#include "heuristica.h"
#include <limits.h>
//TEST
   #include <cstdlib> 
   #include <ctime> 
//ENDTEST

      /**
       * Constructor por defecto
       * */
       Heuristica::Heuristica(){}

   
      /** Constructor
       * @param listado de los rectángulos a empaquetar
       * */
       Heuristica::Heuristica(list<Rectangulo> lista) {
          //cout << "HEURISTICA::Constructor(listado) con lista de tamaño= " << lista.size() << endl;
          candidatos = lista;
          iteracion = iteracionSinCambio = 0 ;
          mejorSol = INT_MAX;
          mejor = solucion = candidatos;
       }

       
         /**
         * Muestra lista de solucion
         * */
         void Heuristica::muestraSolucion() {
            cout << "Listado de solución:" << endl;
            if (solucion.empty()){
               cout << " - vacío - " << endl;
               return;
            }
            list<Rectangulo>::iterator it;
            it = solucion.begin();
	    cout << "Solución: " ;
            while (it != solucion.end()) {
               cout << (*it).getid() << ", ";
               it++;
            }
            cout << endl;
         }
         
         /**
         * Muestra lista de candidatos
         * */
         void Heuristica::muestraCandidatos() {
            cout << "Listado de candidatos:" << endl;
            if (candidatos.empty()){
               cout << " - vacío - " << endl;
               return;
            }
            list<Rectangulo>::iterator it;
            it = candidatos.begin();
	    cout << "Candidato: " ;
            while (it != candidatos.end()) {
               cout << (*it).getid() << ", ";
               it++;
            }
            cout << endl;
         }
         
         
         /**
          * Reinicia la solución
          * */
          void Heuristica::reiniciaSolucion() {
             candidatos = solucion;
             solucion.clear();
          }
       
       /**
        * Cambia un rectangulo de la lista solucion a la lista candidatos
        * @param iterator de list<Rectangulo> con el elemento a mover
        * */
       void Heuristica:: aCandidatos(list<Rectangulo>::iterator itOrigen) {
          //cout << "HEURISTICA::rectACandidatos(it)" << endl;
          candidatos.push_back(*itOrigen);
          solucion.erase(itOrigen);
       }
          
       /**
        * Cambia un rectangulo de la lista candidatos a la lista solucion
        * @param iteratot de list<Rectangulo> con el elemento a mover
        * */
       void Heuristica:: aSolucion(list<Rectangulo>::iterator & itOrigen) {
          //cout << "HEURISTICA::rectASolucion(it)" << endl;
          solucion.push_back(*itOrigen);
          candidatos.erase(itOrigen);
       }

      /** Generar solución inicial 
       * En esta clase base simplemente se meten en orden
       * */
      list<Rectangulo>  Heuristica::generaInicial() {
         //cout << "HEURISTICA::generaInicial()" << endl;
         reiniciaSolucion();
         list<Rectangulo>::iterator it = candidatos.begin();         
         int size = candidatos.size();
         for(int i = 0; i < size ; i++) {
            it = candidatos.begin();
            aSolucion(it);
         }
         
         //cout << "Inicial: " << endl;
         //muestraCandidatos();
         //muestraSolucion();
         
         return solucion;
      }


      /**
      * Mejorar solución
      * En esta clase base se seleccionan aleatoriamente
      * */
      list<Rectangulo> Heuristica::mejoraSolucion() {
         //cout << endl << "HEURISTICA::mejoraSolucion(). Iteracion: " << iteracion << "  Iteración sin mejora: " << iteracionSinCambio << endl;
         list<Rectangulo>::iterator it = candidatos.begin();
         reiniciaSolucion();
         //iteracion++;
         int size = candidatos.size();
         srand((unsigned)time(0));
         for(int i = 0; i < size ; i++) {
            it = candidatos.begin();
            int suma = rand()%candidatos.size();
            for (int j = 0; j < suma; j++) 
               it++;
            aSolucion(it);
         }
         
         //muestraCandidatos();
         //muestraSolucion();
         
         return solucion;
      }


      /**
       * Condición de parada
       * Aquí simplemente comprueba el número de iteraciones
       * */
       bool Heuristica::parada(int valor) {
          iteracion++;
          //cout << "ITERACION: " << iteracion << " con valor: " << valor << endl << endl << endl;
          if (valor < mejorSol) {
             mejorSol = valor;
             mejor = solucion;
             iteracionSinCambio = 0;
          } else {
             iteracionSinCambio++;
          }
          if (iteracion == MAX_ITERACIONES) {
            cout << "Alcanzado máximo de iteraciones: " << MAX_ITERACIONES  << endl;
            return true;
          }
         if (iteracionSinCambio == MAX_ITERACIONES_SIN_CAMBIO) {
            cout << "Alcanzado máximo de iteraciones sin mejora: " << MAX_ITERACIONES_SIN_CAMBIO << endl;
            return true;
         }
         return false;
      }
      
      
      /**
       * Devuelve el valor de la mejor solución
       * */
       int Heuristica::getMejorH() {
          return mejorSol;
       }
      list<Rectangulo> Heuristica::getMejorSol() {
          return mejor;
       }
      
       int Heuristica::getIteracion() {
          return iteracion;
       }
       
       int Heuristica::getIteracionSinCambio() {
          return iteracionSinCambio;
       }
       
       
       
       vector<Solucion> Heuristica::generaConjuntoSoluciones(int S) {
          vector<Solucion> v;
          for (int i = 0; i < S; i++) {
            reiniciaSolucion();
            list<Rectangulo>::iterator it = candidatos.begin();         
            int size = candidatos.size();
            for(int i = 0; i < size ; i++) {
               it = candidatos.begin();
               int rectAlea = rand() % candidatos.size();
               for (int j = 0; j < rectAlea; j++) 
                  it++;
               int giroAlea = rand() % 100;
               if (giroAlea > 50) //Escogemos al azar si ponerlo girado o no
                  it->rotar();
               aSolucion(it);
            }
            Solucion s = Solucion(solucion); //, C.calcularAltura(solucion));
            v.push_back(s);
         }
         return v;
      }
      Solucion Heuristica::MutarSolucion(Solucion & s) {
	      reiniciaSolucion();
	      candidatos = s.getLista();
	      //Elige una posición al azar, y otra posición al azar.
	      int rectAlea = rand() % candidatos.size();
	      list<Rectangulo>::iterator it,it2;
	      it = it2 = candidatos.begin();
	      int rectAlea2;
          do {
	         rectAlea2 = rand() % candidatos.size();
          } while ( rectAlea == rectAlea2);
          //Nos posicionamos en ellas.
	      for (int j = 0; j < rectAlea; j++) 
             it++;
          for (int j = 0; j < rectAlea2; j++) 
             it2++;
          int giroAlea = rand() % 100;
          if (giroAlea > 50) //Escogemos al azar si ponerlo girado o no
                it->rotar();
          giroAlea = rand() % 100;
          if (giroAlea > 50) //Escogemos al azar si ponerlo girado o no
                it2->rotar();
          // Intercambiamos.
          candidatos.insert(it,(*it2));
          candidatos.insert(it2,(*it));
          candidatos.erase(it);
          candidatos.erase(it2);
          Solucion sol = Solucion(candidatos,0);
          return sol;
      }
      /**
       * Combina dos Soluciones a partir del elemento posicion y respetando o no el giro
       * @param origen Solucion a imitar
       * @param destino Solucion que imita
       * @param posicion elemento hasta el que se copia de origen a destino
       * @param giro indica si se imita el giro del origen (1), del destino(-1), o no se modifica (0)
       * */ 
      Solucion Heuristica::combinaSoluciones(Solucion & origen, Solucion & destino, int posicion, int giro) {
         //cout << "HEURISTICA::CombinaSoluciones" << endl;
         list<Rectangulo> original = origen.getLista();
         int size = original.size();

         list<Rectangulo>:: iterator it = destino.getLista().begin();
         list<Rectangulo>:: iterator it2 = original.begin();
         list<Rectangulo> lista;
         for (int i = 0; i < posicion; i++) {
            lista.push_back((*it2));
            it = destino.getLista().begin();
            while ((it->getid() != it2->getid()) && (it != destino.getLista().end()))
               it++;
            if (it->getid() == it2->getid())
               destino.getLista().erase(it);
            it2++;
         }
         size = destino.getLista().size();
         it = destino.getLista().begin();

         for (int i = 0; i < size; i++) {
            lista.push_back((*it));
            it++;
         }
         
         //Imitamos el giro o no
         if ((giro == 1) || (giro == -1)){
            list<Rectangulo> lGiro; 
            if (giro == 1) {
               lGiro = origen.getLista();
            } else if (giro == -1) {
               lGiro = destino.getLista();
            }
            it  = lista.begin();
            it2 = lGiro.begin();

            while (it != lista.end()) {
               if ((it->isRotado()) != (it2->isRotado())) {
                  it->rotar();
               }
               it++;
               it2++;
            } 
         } 
         destino.setLista(lista);
         return destino;
      }

      void Heuristica::intercambiaRectangulo(int id1, int id2, list<Rectangulo> & lista, bool rotar) {

         list<Rectangulo>:: iterator it1,it2,it;
         it = it1 = it2 = lista.begin();
         while ((it != lista.end())) {// && ((it1 == it) || (it2 == it))) {
            if (it->getid() == id1)
               it1 = it;
            if (it->getid() == id2)
               it2 = it;
            it++;
         }       
         
         if (rotar) {
            int aleatorio = rand() % 100;
            if (aleatorio < 50)
               it2->rotar();
            aleatorio = rand() % 100;
            if (aleatorio < 50)
               it1->rotar();
         }
         lista.insert(it1,(*it2));
         lista.insert(it2,(*it1));
         lista.erase(it1);
         lista.erase(it2);               
      }
      
      void Heuristica::intercambiaRectangulo(list<Rectangulo>:: iterator it1, list<Rectangulo>:: iterator it2, list<Rectangulo> & lista) {
         lista.insert(it1,(*it2));
         lista.insert(it2,(*it1));
         lista.erase(it1);
         lista.erase(it2);    
      }
      
      Heuristica::~Heuristica() {
		  //solucion.clear();
		  //candidatos.clear();
		  //mejor.clear();
		  //cout << "HEURISTICA:Destructor" << endl;
	  }
